package leetcode.Hot100;

import java.util.*;

/**
 * @author Cheng Jun
 * Description: 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，
 * 找出 candidates中所有可以使数字和为目标数 target 的唯一组合。
 * <p>
 * candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
 * <p>
 * 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/1 15:43
 * @see coinChange1
 */
public class combinationSum {

    // 结果集合
    static List<List<Integer>> resultList = new ArrayList<>();

    public static void main(String[] args) {
        combinationSum(new int[]{2, 3, 6, 7}, 7);
        combinationSum1(new int[]{2, 3, 6, 7}, 7);
        combinationSum2(new int[]{3, 2, 6, 7}, 7);
    }

    // 完全背包问题：
    // 不行啊，最后会出现 3,2,2  2,3,2  2,2,3 这种情况，还要去重
    // 解答错误，不用看
    @Deprecated
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        HashMap<Integer, List<List<Integer>>> result = new HashMap<>(target);
        List<List<Integer>> outList = new ArrayList<>();
        List<Integer> inList = new ArrayList<>();
        outList.add(inList);
        result.put(0, outList);
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < candidates.length; j++) {
                int diff = i - candidates[j];
                // 差值存在，才能凑成 i
                if (result.containsKey(diff)) {
                    List<List<Integer>> outList1 = result.getOrDefault(i, new ArrayList<>());
                    List<List<Integer>> diffOutList = result.get(diff);
                    for (List<Integer> diffInList : diffOutList) {
                        List<Integer> temp = new ArrayList<>(diffInList);
                        temp.add(candidates[j]);
                        outList1.add(temp);
                    }
                    result.put(i, outList1);
                }
            }
        }
        if (result.containsKey(target)) {
            return result.get(target);
        } else {
            return Collections.emptyList();
        }
    }

    // 逼我用回溯是吧，可还是要去重，有什么好办法去重啊
    // 哈哈哈 被我找到，candidates 每个元素不能往前匹配，因为如果前面匹配过了，再次匹配前面就算重复
    static List<List<Integer>> combinationSum1(int[] candidates, int target) {
        backTrack(candidates, target, new ArrayList<>(), 0);
        return resultList;
    }

    // 注意 ：使用流式操作，每次递归都要计算一遍 candidateList 元素之和 很浪费性能
    // 去重的关键 是 begin，能搜索的下标起始位置
    static void backTrack(int[] candidates, int remains, List<Integer> candidateList, int begin) {
        // Integer sum = candidateList.stream().reduce(0, Integer::sum);
        // if (sum == target) {...}
        if (remains == 0) {
            resultList.add(new ArrayList<>(candidateList));
        } else if (remains < 0) {
            return;
        } else {
            for (int i = begin; i < candidates.length; i++) {
                candidateList.add(candidates[i]);
                backTrack(candidates, remains - candidates[i], candidateList, i);
                candidateList.remove(candidateList.size() - 1);
            }
        }
    }

    // 必杀技：还是完全背包问题 和 零钱兑换 差不多，我就不信搞不出来
    // 思路分析：上面 我们采用了 零钱兑换里面的 内层循环 零钱数组的思路 导致了 结果重复，那我先循环零钱数组，内层再循环 目标数不就行了
    static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> dp[] = new List[target + 1];

        List<List<Integer>> outList = new ArrayList<>();
        List<Integer> inList = new ArrayList<>();
        outList.add(inList);
        for (int i = 1; i < dp.length; i++) {
            dp[i] = new ArrayList<>();
        }
        dp[0] = outList;
        Arrays.sort(candidates);
        for (int i = 0; i < candidates.length; i++) {
            int candidate = candidates[i];
            if (candidate <= target) {
                for (int j = candidate; j <= target; j++) {
                    if (!dp[j - candidate].isEmpty()) {
                        List<List<Integer>> numList = dp[j - candidate];
                        for (List<Integer> integers : numList) {
                            ArrayList<Integer> temp = new ArrayList<>(integers);
                            temp.add(candidate);
                            dp[j].add(temp);
                        }
                    }
                }
            } else {
                // 单个 candidate 都比 target大，又因为 Arrays.sort 所以break
                break;
            }
        }
        return dp[target];
    }
}
